package com.data_structure_algorithm.sort;

import java.util.Arrays;

public class CountSort {
    public static void main(String[] args) {
        int[] arr = {7,9,8,8,5,5,6,2,1,4,7,3,2,5,9,4,5};
        System.out.println("源数组" + Arrays.toString(arr));
        countSort(arr);
    }

    public static int[] countSort(int[] arr) {
        //定义返回值
        int[] res = new int[arr.length];
        //定义计数数组[桶]  累加数组的大小是排序范围
        int[] count = new int[10];
        //遍历数组进行累加
        for (int i = 0; i < arr.length; i++) {
            //某个元素的下标一致，元素每出现一次，对应下标++
            count[arr[i]]++;
        }
        System.out.println("计数数组" + Arrays.toString(count));
        System.out.println();
        System.out.println();
        System.out.println();
        System.out.println();
        //把【计数数组】变成【累加数组】，这两数组等长 首元素不管，次元素是当前元素+前一个元素
        //累加数组的每一个值 等于 计数数组 对应的该下标之前 的所有下标值 相加的结果
        //累加数组的每一个值是对应的计数数组的对应的下标值（元素）在后期排好序的数组中最后出现的位置（比如第8个位置的源数组中的下标为7）
        for (int i = 1; i < count.length; i++) {
            count[i] = count[i] + count[i - 1];
        }

        System.out.println("累加数组" + Arrays.toString(count));

        //倒叙源数组 通过count累加数组记录的相对位置  保证了排序的稳定性
        // --count是因为累加数组的最后出现位置（下标+1） 不是最终数组的下标值，所以要-1
        for (int i = arr.length - 1; i >= 0; i--) {
            res[--count[arr[i]]] = arr[i];
        }
        System.out.println("排序完成" + Arrays.toString(res));
        return res;
    }
}
